# -*-* encoding:UTF-8 -*-
# author            : mengy
# date              : 2019/1/3
# python-version    : Python 3.7.0
# description       : 贪心算法
#  贪心算法的两个性质:
#      1、贪心选择:即原问题的整体最优解可以通过一系列局部最优解得到，应用同一规则将原问题变为一个相似的但规模更小的子问题，而后的每一步都是当前最佳的选择
#      2、最优子结构:一个问题的最优解包含其子问题的最优解

from com.python.algorithm.Sort import Sort

weight = [4, 10, 7, 11, 3, 5, 14, 2]
value = []

if __name__ == '__main__':
    sort = Sort()
    sort.shell_sort(weight)
    print(weight)
    capacity = 30
    pacage = []
    for item in weight:
        if item <= capacity:
            pacage.append(item)
            capacity -= item
    print(pacage)
